#ifndef HEAP_SORT_H
#define HEAP_SORT_H

#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <cmath>

class HeapSort
{
public:
	HeapSort(const unsigned heapSize)
		:	currentHeapSize(heapSize)
	{
		int* data = new int[heapSize];

		srand((unsigned)time(NULL));
		
		printf("unsorted: ");
		for(unsigned i = 0; i < heapSize; ++i)
		{
			data[i] = rand() % 100;
			printf("%d ", data[i]);
		}
		printf("\n");

		buildMaxHeap(data);
		for (unsigned i = currentHeapSize; i > 0; --i) 
		{
			std::swap(data[0], data[currentHeapSize - 1]);
			currentHeapSize--;
			heapify(data, 0);
		}

		printf("sorted: ");
		for(unsigned i = 0; i < heapSize; ++i)
			printf("%d ", data[i]);
		printf("\n");

		delete[] data;
	}

	virtual ~HeapSort()
	{
	}

private:
	unsigned parent(unsigned i) const
	{
		return i - 1 / 2;
	}

	unsigned left(unsigned i) const
	{
		return 2 * i + 1;
	}

	unsigned right(unsigned i) const
	{
		return 2 * i + 2;
	}

	void heapify(int* &a, unsigned i) 
	{
		unsigned greatest;
		unsigned l = left(i);
		unsigned r = right(i);

		if ((a[l] > a[i]) && (l < currentHeapSize)) 
			greatest = l;
		else
			greatest = i;

		if ((a[r] > a[greatest]) && (r < currentHeapSize)) 
			greatest = r;

		if (greatest != i) 
		{
			std::swap(a[i], a[greatest]);
			heapify(a, greatest);
		}
	}

	void buildMaxHeap(int* &a) 
	{
		for (int i = (currentHeapSize - 1) / 2; i >= 0; --i) 
			heapify(a, i);
	}

private:
	unsigned currentHeapSize;
};

#endif